﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TreesLib {
    enum NodeColor { WHITE, RED, BLACK }
    public class NaryNode<T> {
        public static void MakeSet(NaryNode<T> node) {
            node.rank = 0;
            node.parent = node;
        }

        public static void Link(NaryNode<T> node1, NaryNode<T> node2) { // helper method for Tarjan OLLCA
            if (node1.rank > node2.rank) {
                node2.parent = node1;
            }
            else {
                if (node1.rank == node2.rank) {
                    node2.rank++;
                }
            }
        }

        public static void Union(NaryNode<T> node1, NaryNode<T> node2) { // helper method for Tarjan OLLCA
            Link(FindSet(node1), FindSet(node2));
        }

        public static NaryNode<T> FindSet(NaryNode<T> node) { // helper method for Tarjan OLLCA
            if (!node.Equals(node.parent)) {
                node.parent = FindSet(node.parent);
            }
            return node.parent;
        }

        private NodeColor color = NodeColor.WHITE;
        private T data;
        private List<NaryNode<T>> kids = new List<NaryNode<T>>();
        private NaryNode<T> parent;
        private int rank;
        
        public NaryNode(T value) {
            data = value;
        }

        private int Rank {
            get {
                return rank;
            }
            set {
                rank = value;
            }
        }
        
        public NaryNode<T> Parent{
            get {
                return parent;
            }
            set {
                parent = value;
            }
        }
        public T Data {
            get {
                return data;
            }
        }
        public void Clear() {
            kids.Clear();
        }

        public void AddKid(NaryNode<T> kid) {
            kids.Add(kid);
            kid.parent = this;
        }
        public void AddKids(params NaryNode<T>[] newKids) {
            //kids.AddRange(newKids); - can't do this, need to set the parent for each, DRY - the code in AddKid
            foreach (NaryNode<T> newKid in newKids) {
                AddKid(newKid);
            }
        }
        public IList<NaryNode<T>> AllKids {
            get {
                return kids.AsReadOnly();
            }
        }
        public bool hasKids {
            get {
                return kids.Count > 0;
            }
        }

        /// <summary>
        /// Returns string presentation of data only for this node, no children.
        /// </summary>
        /// <returns>ToString of the data on this node including parent info if it's not null and rank if greater than 0.</returns>
        override public string ToString() {
            return Data.ToString() + (parent == null || parent == this ? "" : "<" + parent.data + '>') + (rank == 0 ? "" : "#" + rank);
        }
    }

    public class NaryUtil {

        private static void printNodeSimple<T>(NaryNode<T> node, StringBuilder target) {

            target.Append(node.hasKids ? " {" : " ").Append(node);
            if(node.hasKids) target.Append(':');
            foreach(NaryNode<T> kid in node.AllKids) {
                printNodeSimple(kid, target);
            }
            if(node.hasKids) target.Append('}');
        }
        /// <summary>
        /// Prints the N-ary tree in a very simple although not very presentative way.
        /// </summary>
        /// <param name="root">root of the tree to print</param>
        /// <returns>very simple legible representation of the tree</returns>
        public static string printSimple<T>(NaryNode<T> root) {
            StringBuilder sb = new StringBuilder(1000);
            printNodeSimple(root, sb);
            return sb.ToString();
        }
    }

    public class NarySamples {

        public static NaryNode<string> stringDepth4Kids0to5 {
            get {
                NaryNode<string> root = new NaryNode<string>("R");
                NaryNode<string> Ra = new NaryNode<string>("Ra"), Rb = new NaryNode<string>("Rb"), Rc = new NaryNode<string>("Rc");
                root.AddKids(Ra, Rb, Rc);
                NaryNode<string> RaA = new NaryNode<string>("RaA"), RaB = new NaryNode<string>("RaB"), RaC = new NaryNode<string>("RaC")
                    , RaD = new NaryNode<string>("RaD");
                Ra.AddKids(RaA, RaB, RaC, RaD);

                NaryNode<string> RcA = new NaryNode<string>("RcA"), RcB = new NaryNode<string>("RcB");
                Rc.AddKids(RcA, RcB);

                NaryNode<string> RaAa = new NaryNode<string>("RaAa"), RaAb = new NaryNode<string>("RaAb");
                RaA.AddKids(RaAa, RaAb);

                NaryNode<string> RaBa = new NaryNode<string>("RaBa"), RaBb = new NaryNode<string>("RaBb"), RaBc = new NaryNode<string>("RaBc");
                RaB.AddKids(RaBa, RaBb, RaBc);

                NaryNode<string> RaCa = new NaryNode<string>("RaCa"), RaCb = new NaryNode<string>("RaCb"), RaCc = new NaryNode<string>("RaCc"),
                    RaCd = new NaryNode<string>("RaCd"), RaCe = new NaryNode<string>("RaCe");
                RaC.AddKids(RaCa, RaCb, RaCc, RaCd, RaCe);

                NaryNode<string> RcAa = new NaryNode<string>("RcAa"), RcAb = new NaryNode<string>("RcAb");
                RcA.AddKids(RcAa, RcAb);

                NaryNode<String> RcBa = new NaryNode<string>("RcBa");
                RcB.AddKid(RcBa);
                root.Parent = root;
                return root;
            } // get
        } // stringDepth4Kids0to5
    } // class NarySamples
}
